package com.zxy.leetcode._00600_00699._00600_00609;

/**
 * https://leetcode-cn.com/problems/can-place-flowers/
 *
 * 种花问题
 * 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。
 * 可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 * 给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，
 * 其中 0 表示没种植花，1 表示种植了花。
 * 另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？
 * 能则返回 true ，不能则返回 false。
 */
public class Test00605 {

    public static void main(String[] args) {
        Test00605 test = new Test00605();

        int[] nums1 = {1,0,0,0,1};
        System.out.println(test.canPlaceFlowers(nums1, 1));

        int[] nums2 = {1,0,0,0,1};
        System.out.println(test.canPlaceFlowers(nums2, 2));

        int[] nums3 = {0, 0, 1, 0, 1};
        System.out.println(test.canPlaceFlowers(nums3, 1));

        int[] nums4 = {0, 0, 0};
        System.out.println(test.canPlaceFlowers(nums4, 2));
    }

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }

        int count = 0;
        boolean first = true;
        for (int i=0; i<flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                count ++;
            }else {
                if (first) {
                    n -= count / 2;
                }else {
                    n -= (count-1)/2;
                }

                if (n <= 0) {
                    // 提前结束
                    return true;
                }
                count = 0;
                first = false;
            }
        }

        if (first) {
            n -= (count + 1) / 2;
        }else {
            n -= count / 2;
        }

        return n <= 0;
    }

}
